package Javafoundation;

public class Prim {
    public static void PRIM(int [][] graph,int start,int n){

        int [][] mins=new int [n][2];
        for(int i=0;i<n;i++)
        {
            if(i == start)
            {

                mins[i][0]=-1;

                mins[i][1]=0;

            }else if( graph[start][i]!=-1)
            {

                mins[i][0]=start;

                mins[i][1]= graph[start][i];

            }else{

                mins[i][0]=-1;

                mins[i][1]=Integer.MAX_VALUE;

            }


        }

        for(int i = 0;i < n-1 ; i++)
        {

            int minV = -1, minW = Integer.MAX_VALUE;

            for(int j = 0 ; j < n ; j++)
            {
                if(mins[j][1]!=0 && minW > mins[j][1])
                {

                    minW = mins[j][1];

                    minV=j;

                }

            }


            mins[minV][1] = 0;

            System.out.println("最小生成树的第"+i+"条最小边=<"+(mins[minV][0]+1)+","+(minV+1)+">，权重="+minW);

            for(int j=0 ; j < n ; j++)
            {

                if(mins[j][1] != 0)
                {


                    if( graph[minV][j] != -1 && graph[minV][j] < mins[j][1])
                    {

                        mins[j][0]=minV;

                        mins[j][1]= graph[minV][j];

                    }

                }

            }

        }

    }

    public static void main(String [] args){
        int [][] tree={

                {1,2,3,5,1,1},
                {6,2,5,3,2,1},
                {3,5,2,5,6,4},
                {5,4,5,5,1,2},
                {3,3,6,2,3,6},
                {1,3,4,2,6,1}

        };
        Prim.PRIM(tree, 0, 6);


    }



}
